public class QuickSort {
    public static void quickSort(int[] array) {
        quick(array, 0, array.length - 1);
    }


    private static void quick(int[] array, int left, int right) {
        if (left > right) return;
        int pivot = partition(array, left, right);

        quick(array, left, pivot - 1);
        quick(array, pivot + 1, right);
    }



    /**
     * 挖坑法
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
    private static int partition(int[] array, int left, int right) {
        int key = array[left];

        while (left < right) {
            while (left < right && array[right] >= key) {
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= key) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = key;
        return left;
    }

    /**
     * Hoare 法
     *
     * @param array
     * @param left
     * @param right
     * @return
     */
//    private static int partition(int[] array, int left, int right) {
//        int i = left;
//        int key = array[left];
//        while (left < right) {
//            while (left < right && array[right] >= key) {
//                right--;
//            }
//            while (left < right && array[left] <= key) {
//                left++;
//            }
//            swap(array, left, right);
//        }
//        swap(array, i, left);
//        return left;
//    }

    private static void swap(int[] array, int a, int b) {
        int t = array[a];
        array[a] = array[b];
        array[b] = t;
    }
}
